Devoir 4

(30pts)

Pour ce devoir, vous allez construire la classe générique (avec des templates) faheap. Votre classe sera une dérivation de la classe pqueue dont les fichiers sources sont fournis ici :

Ø pqueue.h

Ø pqueue.cpp

Une faheap est un arbre binaire. Chaque node a 2 nodes fils sauf les nodes feuilles (qui peuvent en avoir 1 ou 0). L’élément à la racine a un niveau de priorité plus élevé que tous ces enfants, ce qui est vrai récursivement pour tous les sous-arbres. La construction d’un objet de type faheap se fait de la manière suivante :

1. ajouter le nouvel element à la fin de la faheap
2. réparer la faheap ("sift up")

 sift_up (node n) {
 while(!is_root(n)) {
  if (priority(n) > priority(parent(n)) {
  swap(n, parent(n) );
 } else break;
 }
 

Insertion des élément 4, 2, 3, 0 et 1 dans cet ordre :

Pour enlever un element (les éléments sont toujours enlevés par ordre de priorité):

1. Mettre le dernier element dans le node racine
2. réparer la faheap ("sift down")

 sift_down(node n) {
 while(true) {
   node child = higher_priority_child(n);
  if (child is null) break
  if (priority(child) > priority(n)) {
  swap(n, child(n));
 } else break;
 }
 

Votre implémentation interne sera basée sur un tableau.

· index du parent(x): (i-1)/2

· index du left_child(x): 2*i + 1

· index du right_child(x): 2*i + 2

La classe faheap devra implémenter les méthodes suivantes définies dans sa classe de base :

• const T& front() const
  T& front()

rend une référence au premier élément de la faheap ou lève une exception de type EMPTY si la faheap est vide.

• const T& second() const

rend une référence au deuxième élément (par ordre de priorité) de la faheap ou lève une exception de type NO_SUCH_ELEMENT si l’élément en question n’existe pas.

• void dequeue()

détruit l’élément de la faheap qui a la plus haute priorité ou lève une exception de type EMPTY si cet élément n’existe pas.

• typename pqueue<T>::handle enqueue(const T&)

Insère un nouvel élément dans l’ordre de priorité ou lève l’exception FULL and returns a handle that could be later used to change the priority of this element. For this method you simply return a null handle, or simply write

 return pqueue<T>::handle(); 
 

The typename keyword is needed for the compiler to take the handle as a type in the signature instead of an instance.

• void priority_change(typename pqueue<T>::handle)

Lève l’exception NOT_IMPLEMENTED;

• void flush()

Vide la faheap

• void length() const

Rend le nombre d’éléments contenus dans la faheap

• bool empty() const

Retourne vrai si la faheap est vide, faux sinon

• void enlarge(int c)

Élargit la capacité interne de la faheap à c éléments, mais seulement si c is plus grand que la capacité présente de la faheap.

• void trim()

Diminue la capacité interne de la faheap au nombre d’éléments qu’elle contient.

Vous devez aussi implémenter les constructeurs, le constructeur par copie, l’opérateur d’assignation et le destructeur. In particulier, vous devrez aussi implémenter le constructeur suivant:

• faheap(bool (*_hp)(const T&, const T&), int _c)

où _hp est un pointer à une fonction qui sera utilisé pour comparer les priorités de deux objets de type T.

 (*hp)(v1,v2) == true
 

Si v1 à une priorité plus élevée que v2

_c est la capacitée initiale

Les fichiers suivants vous sont fournis:

• pqueue.h
• pqueue.cpp
• lheap.h
• faheap.h
• aheap.h
• test.h
• testX.cpp
• X.h
• X.cpp